- pspace-complete
- • potpun prostor
English-Serbian dictionary. 2013.
pspace-complete
Look at other dictionaries:
PSPACE-complete — Mathematicians and computer scientists try to carefully define different types of complexity, and PSPACE complete is one of these types.Roughly, PSPACE is all the problems which can be solved by programs which only need a polynomial (in the… … Wikipedia
List of PSPACE-complete problems — Here are some of the more commonly known problems that are PSPACE complete when expressed as decision problems. This list is in no way comprehensive. Games and puzzles Generalized versions of: Amazons· Atomix· Geography· Gomoku· Hex· Reversi·… … Wikipedia
PSPACE — Unsolved problems in computer science Is P = PSPACE ? PSPACE … Wikipedia
PSPACE-hard — In computational complexity theory, a decision problem p is said to be PSPACE hard if, given any decision problem q in PSPACE, q can be reduced to p in polynomial time. PSPACE hardness is distinguished from PSPACE completeness by the fact that… … Wikipedia
PSPACE-completo — En teoría de la complejidad computacional, la clase de complejidad PSPACE completo (PSPACE complete en inglés) es el subconjunto de los problemas de decisión en PSPACE y todo problema en PSPACE puede ser reducido a él en tiempo polinomial. Los… … Wikipedia Español
Класс PSPACE — В теории сложности вычислений PSPACE набор всех проблем разрешимости, которые могут быть разрешены машиной Тьюринга с полиномиальным ограничением пространства. Содержание 1 Машина Тьюринга с полиномиальным ограничением пространства … Википедия
NP-complete — Euler diagram for P, NP, NP complete, and NP hard set of problems In computational complexity theory, the complexity class NP complete (abbreviated NP C or NPC) is a class of decision problems. A decision problem L is NP complete if it is in the… … Wikipedia
P-complete — In complexity theory, the notion of P complete decision problems is useful in the analysis of both: which problems are difficult to parallelize effectively, and; which problems are difficult to solve in limited space. Formally, a decision problem … Wikipedia
Sharp-P-complete — The correct title of this article is #P complete. The substitution or omission of the # sign is because of technical restrictions. #P complete, pronounced sharp P complete or number P complete is a complexity class in computational complexity… … Wikipedia
co-NP-complete — In complexity theory, computational problems that are co NP complete are those that are the hardest problems in co NP, in the sense that they are the ones most likely not to be in P. If there exists a way to solve a co NP complete problem quickly … Wikipedia
List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… … Wikipedia
